package offer;

import org.omg.PortableInterceptor.INACTIVE;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author ZhanBo
 * @date 2020/6/18
 */
public class Solution59 {

    public static void main(String[] args) {
        MaxQueue maxQueue = new MaxQueue();
        maxQueue.push_back(3);
        maxQueue.push_back(3);
        System.out.println(maxQueue.pop_front());
    }

    /**
     *
     * 面试题59 - I. 滑动窗口的最大值
     *
     * 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
     *
     * 示例:输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
     * 输出: [3,3,5,5,6,7]
     * 解释: 滑动窗口的位置                最大值
     * ---------------               -----
     * [1  3  -1] -3  5  3  6  7       3
     *  1 [3  -1  -3] 5  3  6  7       3
     *  1  3 [-1  -3  5] 3  6  7       5
     *  1  3  -1 [-3  5  3] 6  7       5
     *  1  3  -1  -3 [5  3  6] 7       6
     *  1  3  -1  -3  5 [3  6  7]      7
     *
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0) {
            return new int[0];
        }
        Deque<Integer> deque = new LinkedList<>();
        int[] result = new int[nums.length - k + 1];
        for(int j = 0, i = 1 - k; j < nums.length; i++, j++) {
            // 删除 deque 中对应的 nums[i-1]
            if(i > 0 && deque.peekFirst() == nums[i - 1]) {
                deque.removeFirst();
            }
            while(!deque.isEmpty() && deque.peekLast() < nums[j]) {
                deque.removeLast(); // 保持 deque 递减
            }
            deque.addLast(nums[j]);
            if(i >= 0) {
                // 记录窗口最大值
                result[i] = deque.peekFirst();
            }
        }
        return result;
    }

}





class MaxQueue {

    Queue<Integer> queue;

    LinkedList<Integer> max;

    public MaxQueue() {
        queue = new LinkedList<>();
        //LinkedList是双端链表
        max = new LinkedList<>();
    }

    public int max_value() {
        return max.size()==0?-1:max.getFirst();
    }

    public void push_back(int value) {
        queue.add(value);
        //注意：这里第二个判断条件不能带等号，即max中对于当前queue中的具有相同值的元素会全部存储，而不是存储最近的那个。
        while(max.size()!=0 && max.getLast()<value){
            max.removeLast();
        }
        max.add(value);
    }

    public int pop_front() {
        //Integer类型的值的比较不能直接使用==
        //如果移除的是当前队列中的最大值，则修改最大值的队列
        if(max.size()!=0 && queue.peek().equals(max.getFirst()))
        {
            max.removeFirst();
        }
        //出队头
        return queue.size()==0?-1:queue.poll();
    }

}
